使用软件方法利用 ILP I
AP SHANTHI博士
本模块的目标是讨论用于开发 ILP 的软件方法。详细讨论了循环展开的概念。
自大约 1985 年以来，所有处理器都使用流水线来重叠指令的执行并提高处理器的性能。指令之间的这种重叠称为指令级并行性，因为可以并行评估指令。有两种可分离的技术来利用 ILP：
动态并依赖于硬件来定位并行性
静态且更多地依赖软件
编译器采用静态技术来提高性能。主要使用硬件方法的处理器在这些优化之上使用其他技术来提高性能。动态的、硬件密集型方法主导了 PIII、P4 等处理器，甚至是 i3、i5 和 i7 等最新处理器。软件密集型方法用于像安腾这样的处理器。
我们知道，
管道 CPI = 理想管道 CPI + 结构停顿 + 数据危险停顿 + 控制危险停顿
在理想的管道CPI是由实现最大性能可达到的指标。
当我们考虑执行优化时，如果只考虑基本块，那么编译器和硬件都没有太多选择。一个基本块是一个直线代码序列，除了入口处没有分支进入，除了出口处没有分支出。由于平均动态分支频率为 15% 到 25%，我们通常只有 4 到 7 条指令在一对分支之间执行。此外，基本块中的指令很可能相互依赖。因此，基本块没有为利用 ILP 提供太多空间。为了获得实质性的性能增强，我们必须跨多个基本块利用 ILP。开发并行性的最简单方法是探索循环级并行性，以开发循环迭代之间的并行性。矢量架构是处理循环级并行的一种方式。否则，我们将不得不查看利用循环级并行性的动态或静态方法。常用的方法之一是循环展开，通过硬件动态分支预测，或由编译器使用静态分支预测静态地展开。
在执行此类优化时，硬件和软件都必须保持程序顺序。也就是说，如果顺序执行，一次一个，由原始源程序确定，指令的执行顺序应该保持不变。数据流，即产生结果的指令和使用结果的指令之间数据值的实际流动，应该得到维护。此外，只有当指令中使用的名称发生变化时，名称相关性中涉及的指令才能同时执行，以使这些指令不会发生冲突。这是通过寄存器重命名的概念完成的。这解决了寄存器的名称依赖性。这可以再次由编译器或硬件完成。保留异常行为，即
在前面的模块中，我们研究了硬件如何完成动态调度，其中硬件动态展开循环。在本模块中，我们将讨论编译器如何通过循环的静态展开来利用循环级并行性。确定指令依赖性对于循环级并行性至关重要。如果两条指令是
并行，它们可以在任意深度的管道中同时执行而不会造成任何停顿（假设没有结构危险）
依赖，它们不是并行的，必须按顺序执行，尽管它们可能经常部分重叠。
让我们考虑以下迭代循环和与之等效的程序集。
for(i=1;i<=1000;i++)
x(i) = x(i) + s;
Loop: LD F0,0(R1) ;F0=向量元素
ADDD F4,F0,F2 ;从 F2 添加标量
SD 0(R1),F4 ;存储结果
SUBI R1,R1,8 ;指针递减8bytes (DW)
BNEZ R1,Loop ;branch R1!=0
NOP ;延迟分支槽
循环体由三个指令组成，每个指令都相互依赖。循环中的真实数据依赖性如下所示。另外两条指令称为循环维护代码。
Loop: LD F0,0(R1) ;F0=向量元素
ADDD F4,F0,F2 ;在F2中添加标量
SD 0(R1),F4 ;存储结果
SUBI R1,R1,8 ;递减指针8B (DW)
BNEZ R1,Loop ;branch R1!=0
NOP ;延迟分支槽
出于讨论的目的，让我们考虑以下一组延迟：
指令产生结果 使用结果说明 时钟周期的延迟
FP ALU 操作 另一个 FP 操作 3
FP ALU 操作 存储双 2
加载双倍 FP ALU 操作 1
加载双倍 存储双 0
整数运算 整数运算 0
原始调度：如果我们尝试为上述延迟调度代码，调度可以如下所示。第一条和第二条从属指令之间有一个停顿，Add 和从属 Store 之间有两个停顿。在循环维护代码中，由于 Sub 和 Branch 之间的数据依赖关系，也需要引入一个档位。最后一个停顿用于分支指令，即分支延迟槽。循环的一次迭代需要十个时钟周期来执行。
1 循环：LD F0, 0(R1) ;F0=向量元素
2档
3 ADDD F4, F0, F2 ;在F2中添加标量
4档
5档
6 SD 0(R1), F4 ;存储结果
7 SUBI R1, R1, 8 ;递减指针 8 字节 (DW)
8档
9 BNEZ R1, Loop ;branch R1!=0
10stall ;延迟分支槽
重新组织代码的计划：编译器可以尝试通过重新组织代码来优化计划。它标识可以将 Sub 指令向前移动，并适当修改 Store 地址并将其放入分支延迟槽中。重组后的代码如下所示。每次循环迭代只需要六个时钟周期。只有一个摊位。
1 回路：LD F0,0(R1)
2 苏比 R1,R1,8
3 添加 F4,F0,F2
4档
5 BNEZ R1,Loop ;延迟分支
6 SD 8(R1),F4 ;经过SUBI时改变
展开且未重组的循环： 现在，让我们假设循环展开了四次。在展开循环时，我们必须记住，复制循环体的目的是生成足够数量的并行指令。因此，除了真正的数据依赖之外，所有的名称依赖都必须通过寄存器重命名来消除。此外，由于循环体被复制，涉及分支指令（控制依赖）的循环维护代码在复制迭代中消失了。观察下面显示的代码。您可以看到不同的目标寄存器已用于各种加载操作（F0、F6、F10、F14）、加法操作（F4、F8、F12、F16），并且加载和存储指令的地址已被适当修改为0(R1)、-8(R1)、-16(R1) 和 -24(R1)。循环的展开版本没有循环维护代码，最后一个循环维护代码将地址修改为 -32，适当地设置它以执行第五次迭代。但是，这些展开的指令没有正确调度，您会发现调度代码中存在许多停顿。此代码需要 28 个时钟周期，或每次迭代 7 个。
1 回路：LD F0,0(R1)
2档
3 添加 F4,F0,F2
4档
5档
6 SD 0(R1),F4
7 LD F6,-8(R1)
8档
9 添加 F8,F6,F2
10档
11档
12 SD -8(R1),F8
13 LD F10,-16(R1)
14档
15 添加 F12,F10,F2
16档
17档
18 SD -16(R1),F12
19 LD F14,-24(R1)
20档
21 添加 F16,F14,F2
22档
23档
24 SD -24(R1),F16
25 苏比 R1,R1,#32
26 BNEZ R1,LOOP
27档
28 NOP
展开和重新组织的循环：我们现在将看看如何通过重新组织代码来正确安排展开的指令。这如下所示。观察到所有相关指令都已分离，导致无停顿调度，每次迭代仅占用 3.5 个时钟周期。
1 回路：LD F0,0(R1)
2 LD F6,-8(R1)
3 LD F10,-16(R1)
4 LD F14,-24(R1)
5 添加 F4,F0,F2
6 添加 F8,F6,F2
7 添加 F12,F10,F2
8 添加 F16、F14、F2
9 SD 0(R1),F4
10 SD -8(R1),F8
11 SD -16(R1),F12
12 苏比 R1,R1,#32
13 BNEZ R1,LOOP
14 SD 8(R1),F16 ; 8-32 = -24
展开循环多少次？即使我们不知道循环的上限，假设它是 n，并且我们希望展开循环以制作 k 个主体的副本。因此，我们生成了一对连续的循环，而不是单个展开的循环：
– 第 1 次执行 (n mod k) 次并具有原始循环的主体
– 第二个是由迭代 (n/k) 次的外部循环包围的展开体
例如，如果我们要执行 100 次循环并且我们能够展开 6 次，那么展开的 6 次循环将迭代 16 次，占 96 次迭代，其余 4 次迭代将使用原始循环滚动循环。对于较大的 n 值，大部分执行时间将花费在展开的循环中，从而提供具有大量独立指令的优势，从而为编译器提供充足的机会进行适当的调度。
循环展开时要记住的要点：展开循环时要记住的一般要点如下：
确定在SUBI和BNEZ之后移动SD是合法的，并找到调整SD偏移量
通过发现循环迭代是独立的，除了循环维护代码之外，确定展开循环是有用的
使用不同的寄存器以避免不必要的约束，因为不同的计算使用相同的寄存器会强制这些约束
消除额外的测试和分支并调整循环维护代码
通过观察来自不同迭代的加载和存储是独立的，确定展开循环中的加载和存储可以互换。这需要分析内存地址并发现它们引用的不是同一个地址
调度代码，保留产生与原始代码相同的结果所需的任何依赖性。
然而，循环展开是有限制的。他们是：
每次额外展开时摊销的开销金额减少
阿姆达尔收益递减定律
当我们展开循环四次时，它在指令之间产生了足够的并行性，可以在没有停顿周期的情况下调度循环。实际上，在 14 个时钟周期中，只有 2 个周期是循环开销：维护索引值的 Sub 和终止循环的分支。如果循环展开八次，则开销从每次原始迭代的 1/ 2 个循环减少到 1/ 4
代码大小的增长
对于较大的循环，它会极大地增加代码大小，如果指令缓存未命中率增加，则成为一个值得关注的问题
注册压力
激进的展开和调度造成的寄存器可能会出现短缺。这会导致注册压力。随着实时值数量的增加，可能无法将所有实时值分配给寄存器，我们可能会失去展开的部分或全部优势。
循环展开因此减少了分支对管道的影响。另一种选择是使用分支预测。
编译器对代码移动的看法：编译器只关心程序中的依赖性，而不关心硬件危险是否依赖于给定的管道。它试图调度代码以避免危险。需要记住以下几点。
编译器查找数据相关性（硬件的 RAW 危害）
– 指令 i 产生指令 j 使用的结果，或
– 指令j是依赖于指令k的数据，指令k是依赖于指令i的数据。
如果有依赖，我们就不能并行执行这些指令
– 很容易确定寄存器（固定名称）
– 难以解析内存位置，因为 32(R4) 和 20(R6) 可能指的是相同的有效地址或不同的有效地址。
– 另外，从不同的循环迭代中，编译器不知道 20(R6) 和 20(R6) 是指相同的有效地址还是不同的有效地址。
另一种依赖称为名称依赖：
两条指令使用相同的名称（寄存器或内存位置）但不交换数据
– 反依赖（如果对硬件有危害则为 WAR）
指令 j 写入一个寄存器或内存位置，指令 i 从中读取并首先执行指令 i
– 输出依赖性（如果对硬件有危害，则为 WAW）
指令 i 和指令 j 写入相同的寄存器或内存位置；指令之间的顺序必须保留。
最后一种依赖称为控制依赖
- 例子
如果 p1 {S1;};
如果 p2 {S2;};
S1 控制依赖于 p1，S2 控制依赖于 p2 但不依赖于 p1。
控制依赖的两个（明显）约束：
控制依赖于分支的指令不能移动到分支之前，因此它的执行不再受分支控制，并且
不依赖于分支的控制指令不能移动到分支之后，因此它的执行由分支控制。
可以放宽控制依赖以获得并行性，前提是它们保留异常顺序（使用前由分支检查寄存器中的地址）和数据流（寄存器中的值取决于分支）
在我们考虑的示例循环中，我们着眼于处理所有这些问题。寄存器被重命名为加载、添加和存储指令。通过复制循环消除了控制依赖性。此外，我们的示例要求编译器知道，如果 R1 不变，则 0(R1) ≠ -8(R1) ≠ -16(R1) ≠ -24(R1)。一些负载和存储之间没有依赖关系，因此它们可以相互移动。更重要的是，我们考虑的循环没有任何循环携带依赖。如果我们考虑下面给出的循环，其中 A、B、C 是不同且不重叠的，
for(i=1;i<=100;i=i+1){
A[i+1]=A[i]+C[i]；/*S1*/
B[i+1]=B[i]+A[i+1];/*S2*/
}
S2 使用由 S1 在同一次迭代中计算的值 A[i+1]
S1 使用 S1 在较早的迭代中计算出的值，因为迭代 i 计算了在迭代 i+1 中读取的 A[i+1]。对于 B[i] 和 B[i+1]，S2 也是如此。
这是迭代之间的“循环携带依赖”，这意味着迭代是相关的，不能并行执行。
编译器可以很聪明，可以识别和消除名称依赖性，确定哪些循环可能包含并行性并产生良好的代码调度。
总而言之，我们已经看到编译器可以在循环中利用 ILP，而无需循环携带依赖。循环展开是一种利用 ILP 的常用方法，名称依赖是通过寄存器重命名来处理的。
网页链接/支持材料
计算机组织与设计——硬件/软件接口，David A. Patterson 和 John L. Hennessy，第 4 版，Morgan Kaufmann，Elsevier，2009 年。
Computer Architecture – A Quantitative Approach，John L. Hennessy 和 David A. Patterson，第 5 版，Morgan Kaufmann，Elsevier，2011。